package LeetCode.Sort;

import java.util.Arrays;
import java.util.Comparator;

public class MergeSort {
    public static void merge_sort(int a[], int first, int last, int temp[]) {

        if (first < last) {
            int middle = (first + last) / 2;
            merge_sort(a, first, middle, temp);//左半部分排好序
            merge_sort(a, middle + 1, last, temp);//右半部分排好序
            mergeArray(a, first, middle, last, temp); //合并左右部分
        }
    }

    public static void mergeArray(int[] a, int first, int middle, int end, int[] temp) {
        int i = first;
        int m = middle;
        int j = middle + 1;
        int n = end;
        int k = 0;
        while (i < m && j < n) {
            if (a[i] < a[j]) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
            }
        }

        while (i < m) {
            temp[k++] = a[i++];
        }
        while (j < n) {
            temp[k++] = a[j++];
        }

        for (int ii = 0; ii < k; ii++) {
            a[first + ii] = temp[ii];
        }
    }

    public static void merge(Comparable[] arr, int l, int mid, int r) {
        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);

        int i = l;
        int j = mid + 1;
        int k = l;

        while (i <= mid && j <= r) {
            if (aux[i - l].compareTo(aux[j - l]) > 0) {
                arr[k++] = aux[j - l];
                j++;
            } else {
                arr[k++] = aux[i - l];
                i++;
            }
        }

        while (i <= mid) {
            arr[k++] = aux[i - l];
            i++;
        }
        while (j <= r) {
            arr[k++] = aux[j - l];
            j++;
        }


//        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);
//
//        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
//        int i = l, j = mid + 1, k =l;
//        while(k <= r) {
//            if (i > mid) {  // 如果左半部分元素已经全部处理完毕
//                arr[k++] = aux[j++];
//                j++;
//            } else if (j > r) {   // 如果右半部分元素已经全部处理完毕
//                arr[k++] = aux[i++];
//                i++;
//            } else if (aux[i - l].compareTo(aux[j - l]) < 0) {  // 左半部分所指元素 < 右半部分所指元素
//                arr[k++] = aux[i - l];
//                i++;
//            } else {  // 左半部分所指元素 >= 右半部分所指元素
//                arr[k++] = aux[j - l];
//                j++;
//            }
//        }

    }

    public static void sort(Comparable[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (r + l) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        if (arr[mid].compareTo(arr[mid + 1]) > 0) {
            merge(arr, l, mid, r);
        }
    }

    public static void sort(Comparable[] arr) {

        int n = arr.length;
        sort(arr, 0, n - 1);
    }

    // 测试MergeSort
    public static void main(String[] args) {

        Integer[] arr = new Integer[]{10, 4, 7, 2, 3, 5, 8, 9};
        sort(arr);
        //打印数组
        Arrays.asList(arr).stream().forEach(System.out::println);
    }

    // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
//    private static void merge(Comparable[] arr, int l, int mid, int r) {
//
//        Comparable[] aux = Arrays.copyOfRange(arr, l, r + 1);
//
//        // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
//        int i = l, j = mid + 1;
//        for (int k = l; k <= r; k++) {
//
//            if (i > mid) {  // 如果左半部分元素已经全部处理完毕
//                arr[k] = aux[j - l];
//                j++;
//            } else if (j > r) {   // 如果右半部分元素已经全部处理完毕
//                arr[k] = aux[i - l];
//                i++;
//            } else if (aux[i - l].compareTo(aux[j - l]) < 0) {  // 左半部分所指元素 < 右半部分所指元素
//                arr[k] = aux[i - l];
//                i++;
//            } else {  // 左半部分所指元素 >= 右半部分所指元素
//                arr[k] = aux[j - l];
//                j++;
//            }
//        }
//    }
//
//    // 递归使用归并排序,对arr[l...r]的范围进行排序
//    private static void sort(Comparable[] arr, int l, int r) {
//        if (l >= r) {
//            return;
//        }
//        int mid = (l + r) / 2;
//        sort(arr, l, mid);
//        sort(arr, mid + 1, r);
//        // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
//        // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
//        if (arr[mid].compareTo(arr[mid + 1]) > 0)
//            merge(arr, l, mid, r);
//    }
//
//    public static void sort(Comparable[] arr) {
//
//        int n = arr.length;
//        sort(arr, 0, n - 1);
//    }

    // 测试MergeSort
//    public static void main(String[] args) {
//
//        int N = 1000;
//        Integer[] arr = new Integer[]{10,4,7,2,3,5,8,9};
//        sort(arr);
//        //打印数组
//        for (Integer integer : arr) {
//            System.out.println(integer);
//        }
//    }


}
